Super, das ist Fette nach. Ich würde sagen, wir fangen an. Sie sehen, ich bin

nicht Professor Schröder. Mein Name ist Dominik Deuber. Ich bin Postdoctorant

am Lerstuhl und organisiere zusammen mit Professor Schröder und Julian Kotsuo

die Vorlesung. Und ich darf heute mit Ihnen weiter Sortieralgerortment anschauen.

Ich versuche das vom Stil her genauso zu machen wie Professor Schröder, dass sie nicht ganz irritiert sind.

Hier fängt er immer mit einem Rückblick an. Das machen wir auch.

Kann man jemand von Ihnen sagen, was Sie letzte Stunde gemacht haben.

Ist eine Woche her? Ich weiß. Gäste einmal Feiertag, aber

sollte auch nichts ändern.

Also, weiß jemand, was das Ausgangsproblem von Sortieren ist. Was wollen Sie beim Sortieren erreichen?

Kann man das hier sagen? Trauen Sie sich?

Das Ausgangsproblem ist, Sie haben eine Sequenz von N-Elementen. Das war einmal noch ein paar mehr.

Das ist unser Tiert. Die wollen sie jetzt sortieren. Das heißt, das Ziel ist, wollen irgendwie

diese Elemente algorithmisch in eine sortierte Sequenz überführen.

Mach mal das mal gerade hier ein Beispiel.

Das ist wieder zu wenig Platz. Das ist die Ausgangssituation.

Sie haben sich letzte Stunde schon einige Sortieralgerortment angeschaut.

Weißt man, hier ein Welche.

Hier ändert sich jemand an Bogo-Sort.

Bogo-Sort ist ein denkbar ungünstiger Algorithm. Ich habe einen Katspiel mitgebracht,

dass ich das etwas besser vorstellen kann. Bogo-Sort wäre so, wie wenn Sie das Katspiel

in die Luft werfen. Dann fallen alle Karten runter, sie gehen hinsammen, die auf und gucken

absurdiert ist. Denkbar schlechte Idee. Aber Sie können natürlich Glück haben.

Das ist auf den ersten Schlag sortiert. Also im Bestcase schaffen Sie eine Laufzeit von O von N.

Sie haben sich noch einen anderen Sortieralgerortmus angeschaut. Den schauen wir uns gleich noch

mal ein bisschen genauer an, nämlich Slow-Sort. Und dann haben Sie sich Eigenschaften angeschaut.

Was kann man über Sortieralgerortmenten aussagen? Dann haben Sie sich vier Stück angeschaut.

Sie können mal während ich hier aufschreiben, nachdenken, welche vier das noch mal waren.

Weißen wir, haben Sie eine vier Eigenschaften. Was haben Sie die ersten paar Wochen gemacht?

Laufzeitanalyse, wenn er jemanden sich hier... Das ist das erste, was Sie natürlich machen

können. Sie können sich die Zeitkomplexität anschauen. Was wir gerade gesagt haben,

also das Kartespielen, die Luft werfen, wieder aufsammeln, das kann sehr, sehr, sehr lange dauern.

Es gibt Alggerortmenten, die wir es nicht schneller machen. Genau, Speicher. Das ist ganz wichtig.

Es nänder sich immer Platzkomplexität. Schauen wir uns später auch noch mal an.

Wir täuten auch eine etwas größere Rolle spielen. Was haben die Alggerortmenten, die Sie bisher

angeschaut haben, alle gemacht? Ja? Ja, genau. Die haben sortiert. Und was haben Sie dabei gemacht?

Vielleicht auch Sie noch mal, was haben die Alggerortmenten gemacht? Was haben Sie sich angeschaut?

Genau, verglichen. Ja, das waren vergleichsbasierte Alggerortmenten. Das spielt auch eine

größere Rolle, denn Sie werden nächste Woche sehen, dass es auch Alggerortmenten gibt,

die ein bisschen mehr noch machen und dadurch ein Laufzeit gewinnen haben. Also vergleichsbasiert.

Beziehungsweise nicht vergleichsbasiert. Okay, und das letzte? Weißt es noch jemand? Stichwo, ja.

Genau, das nennt sich Stabilität. Das haben Sie auch noch angeschaut. Und das ist auch wichtig,

weil Sie ein Zweifel wollen, dass Ihr sortieragortment stabil ist. Genau, das waren die Eigenschaften.

Was haben Sie ganz am Ende der Stunde gemacht? Was ist das noch jemand? Stichwort untere Schranke?

Nee. Könnte man meinen, aber nee, unterrechschranke? Ja, Sie haben sich eine unterrechschranke für die

Worstcase Laufzeit von Sortieragortmenten angeschaut. Also, das ist ja auch für die Vergleiche, die

benötigen. Und wie viele Vergleiche brauchen, Vergleichsbasierte Sortieragortmenten in Worstcase?

Genau. Wir schreiben das natürlich hier wieder mit Omega, Omega N-Log N, viele Vergleiche. Das heißt,

wenn Sie Vergleichsbasiert sortieren, können Sie im Worstcase nicht schneller sein als N-Log N.

Das ist wichtig, die unterrechschranke. Und es führt uns auch direkt zu dem, was wir heute machen,